#[test]
fn test_longest_palindrome() {
    assert_eq!(longest_palindrome("babad".to_string()), "aba");
    assert_eq!(longest_palindrome("cbbd".to_string()), "bb");
    assert_eq!(longest_palindrome("a".to_string()), "a");
    assert_eq!(longest_palindrome("ac".to_string()), "c");
}
/*
   5. 最长回文子串
   给你一个字符串 s，找到 s 中最长的回文子串。

   示例 1：
   输入：s = "babad"
   输出："bab"
   解释："aba" 同样是符合题意的答案。

   示例 2：
   输入：s = "cbbd"
   输出："bb"

   示例 3：
   输入：s = "a"
   输出："a"

   示例 4：
   输入：s = "ac"
   输出："a"

   提示：
   1 <= s.length <= 1000
   s 仅由数字和英文字母（大写和/或小写）组成
*/
pub fn longest_palindrome(s: String) -> String {
    let n = s.len();
    let mut dp = vec![vec![false; n]; n];
    let mut res = String::new();
    let s: Vec<char> = s.chars().collect();
    let mut max_len = 0;
    
    for i in (0..n).rev() {
        for j in i..n {
            if s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) {
                dp[i][j] = true;

                if j - i + 1 > max_len {
                    res = s[i..j + 1].iter().collect();
                    max_len = j - i + 1;
                }
            }
        }
    }
    return res;
}
